package leetcode_递归;

/**
 * 汉诺塔
 * 要把最下层的东西放到 c 上，必须先把上层的东西先放到 c 上才行
 * 算法：
 *   递归
 *   先把 n - 1 个盘子从 a 移动到 b 上
 *   再把第 n 个盘子从 a 移动到 c 上
 *   再把 n - 1 个盘子从 b 移动到 c 上
 */
public class _汉诺塔 {

    static int times;

    public static void main(String[] args) {
        new _汉诺塔().hannoi(4, 'a', 'b', 'c');
    }

    public void move(int disk, char M, char N) {
        System.out.println("第" + (++times) + "次移动, 盘子" + disk + "  " + M + "------->" + N);
    }


    public void hannoi(int n, char A, char B, char C) {
        if (n == 1) {
            move(n, A, C);
        } else {
            //移动上一关的步骤移动到 B
            hannoi(n - 1, A, C, B);
            //把最大的盘子移动 C 塔
            move(n, A, C);
            //再把 B 上的上一关的盘子移动到 C 上就可以了
            hannoi(n - 1, B, A, C);
        }
    }
}
